package leetcode20;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

/**
 * @Author tyy
 * @Description 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

    示例 1：
    输入：s = "()"
    输出：true
 * @Since 2021/10/5
 */
public class Solution {
    public boolean isValid(String s) {
        while (true) {
            if (s.contains("()") || s.contains("{}") || s.contains("[]")) {
                s = s.replace("()", "").replace("{}", "").replace("[]", "");
            }else{
                return "".equals(s);
            }
            /*while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
                s = s.replace("()", "").replace("{}", "").replace("[]", "");
            }
            return "".equals(s) ? true : false;*/
        }
    }
    public boolean isValid2(String s) {
        if(s.length()==0) return true;
        Stack<Character> stack = new Stack<>();
        stack.push('?');//为了防止栈中元素都弹出去了再执行pop()方法报错。
        for(char c : s.toCharArray()){
            if(c=='(') stack.push(')');
            else if(c=='{') stack.push('}');
            else if(c=='[') stack.push(']');
            else if(c!=stack.pop()) return false;
        }
        return stack.size()==1;
    }

    private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};
    public boolean isValid3(String s) {
        if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;
        LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};
        for(Character c : s.toCharArray()){
            if(map.containsKey(c)) stack.addLast(c);
            else if(map.get(stack.removeLast()) != c) return false;
        }
        return stack.size() == 1;
    }
    public boolean isValid4(String s) {
        if(s.isEmpty())
            return true;
        Stack<Character> stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        if(stack.empty())
            return true;
        return false;
    }

    public static void main(String[] args) {
        String s = "()[]{}";
        boolean valid = new Solution().isValid2(s);
        System.out.println("i = " + valid);
        s = "([)]";
        System.out.println("new Solution().isValid(s) = " + new Solution().isValid3(s));
//        s = "{[]}";
//        System.out.println("new Solution().isValid(s) = " + new Solution().isValid(s));


    }
}
